package com.example.demo.leetcode.top100;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _64搜索二维矩阵
 * @description
 * @date 2023/06/23 10:27
 * <p>
 * ******************************************************
 */
public class _64搜索二维矩阵 {

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int left_bound = 0;
        int top_bound = 0;
        int right_bound = n - 1;
        int bottom_bound = m - 1;

        while (top_bound < bottom_bound) {
            int mid_row = bottom_bound - (bottom_bound - top_bound) / 2;
            if (target > matrix[mid_row][0]) {
                top_bound = mid_row;
            } else if (target < matrix[mid_row][0]) {
                bottom_bound = mid_row -1;
            } else {
                return true;
            }
        }
        if (top_bound == bottom_bound) {
            while (left_bound <= right_bound) {
                int mid_col = right_bound - (right_bound - left_bound) / 2;
                if (target > matrix[top_bound][mid_col]) {
                    left_bound = mid_col + 1;
                } else if (target < matrix[top_bound][mid_col]) {
                    right_bound = mid_col -1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        _64搜索二维矩阵 s = new _64搜索二维矩阵();
        System.out.println(s.searchMatrix(new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}}, 3));
    }
}
